package com.yincb.sort;


import java.util.Arrays;

/**
 * 归并排序
 */
public class MegrSort {


    public static void main(String[] args) {
        int data[] = {9, 5, 6, 8, 0, 3, 7, 1};

        megerSort(data, 0, data.length - 1);

        System.out.println(Arrays.toString(data));

    }

    public static void megerSort(int[] data, int left, int right) {
        int temp[] = new int[data.length];  //临时数组用来保存合并的数据
        if (left < right) {
            int mid = (left + right) / 2;
            megerSort(data, left, mid);
            megerSort(data, mid + 1, right);

            meger(data, left, mid, right, temp);
        }
    }

    private static void meger(int[] data, int left, int mid, int right, int[] temp) {
        int point1 = left;      //  左边指针
        int point2 = mid + 1; // 右边指针
        int t = 0;
        while (point1 <= mid && point2 <= right) {
            if (data[point1] <= data[point2]) {
                temp[t] = data[point1];
                point1++;
                t++;
            } else {
                temp[t] = data[point2];
                point2++;
                t++;
            }
        }

        while (point1 <= mid) { //将左边剩余元素填充进temp中
            temp[t] = data[point1];
            t++;
            point1++;
        }
        while (point2 <= right) {//将右序列剩余元素填充进temp中
            temp[t] = data[point2];
            t++;
            point2++;
        }

        t = 0;
        while (left <= right) {
            data[left] = temp[t];
            left++;
            t++;
        }

    }
}

